// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-15 21:09
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE.segTree;

import org.junit.jupiter.api.Test;

/**
 * 区间和个数计算
 * 查询线段树中位于指定区间的节点数量
 */
public class CountRangeSum {
    public final int N = (int) 1e+5;
    Node root;
    public int[] preFix;

    public class Node {
        int l, r;
        Node left, right;
        int value;

        public Node(int l, int r, int value) {
            this.l = l;
            this.r = r;
            this.value = value;
        }
    }

    public Node buildTree(int l, int r) {
        /*-----使用前缀和数组可以快速查找区间和-----*/
        Node node = new Node(l, r, preFix[r + 1] - preFix[l]);
        if (l == r) {
            return node;
        }
        int mid = l + r >> 1;
        node.left = buildTree(l, mid);
        node.right = buildTree(mid + 1, r);
        return node;
    }

    public void setPreFix(int[] sum) {
        this.preFix = sum;
    }

    public int travelSeg(Node root, int lower, int upper) {
        if (root == null) {
            return 0;
        }
        int ans = travelSeg(root.left, lower, upper) + travelSeg(root.right, lower, upper);
        if (lower <= root.value && root.value <= upper) {
            return 1 + ans;
        } else {
            return ans;
        }
    }


    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        /*-----前缀和和构造，便于线段树节点值更新-----*/
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        setPreFix(sum);
        root = buildTree(0, n - 1);
        /*-----遍历线段树，并返回计算值-----*/
        return travelSeg(root, lower, upper);
    }

    @Test
    public void shout() {
        int[] nums = {0, 5, 3};
        int lower = 0, upper = 8;
        System.out.println(countRangeSum(nums, lower, upper));
    }
}
